package com.base.binarytree;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 437. 路径总和 III
 *
 * 给定一个二叉树的根节点 root，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
 *
 * 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/path-sum-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author leon
 * @date 2021年09月28日 10:49
 */
public class PathSum3 {


    /**
     * 先序遍历:
     * 通过dfs1遍历所以结点，通过dfs2判断从当前结点，到其根结点过程中，是否有满足和为target的情况。
     * @param root
     * @param target
     * @return
     */
    int ans = 0,t;
    public int pathSum(TreeNode root,int target){
        t = target;
        dfs1(root);
        return ans;
    }

    void dfs1(TreeNode root){
      if (root == null){
          return;
      }
      dfs2(root,root.val);
      dfs1(root.left);
      dfs1(root.right);

    }

    void dfs2(TreeNode root,int val){
        if (val == t){
            ans++;
        }
        if (root.left!= null){
            dfs2(root.left,root.left.val+val);
        }
        if (root.right != null){
            dfs2(root.right,root.right.val+val);
        }

    }
}
